package 力扣;

import java.util.ArrayList;
import java.util.List;

/**
 给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
 candidates 中的数字可以无限制重复被选取。
 说明：
 所有数字（包括 target）都是正整数。
 解集不能包含重复的组合。 
 示例 1：
 输入：candidates = [2,3,6,7], target = 7,
 所求解集为：
 [
 [7],
 [2,2,3]
 ]
 示例 2：
 输入：candidates = [2,3,5], target = 8,
 所求解集为：
 [
   [2,2,2,2],
   [2,3,3],
   [3,5]
 ]
 */

public class _39组合总和 {

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        //回溯法
        ArrayList<List<Integer>> ret = new ArrayList<>();
        back(ret,candidates,target,new ArrayList<Integer>(),0);
        return ret;
    }

    private void back(ArrayList<List<Integer>> ret, int[] candidates, int target, ArrayList<Integer> list,Integer start) {
        if(target == 0){
            ret.add(new ArrayList<Integer>(list));
            return;
        }
        for (int i = start; i < candidates.length; i++) {
            if( candidates[i] <= target){
                list.add(candidates[i]);
                back(ret,candidates,target - candidates[i] ,list,i);
                list.remove(list.size()-1);
            }
        }

    }

}
